#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-18 9:41 上午
# @Author  : yangdy
# @File    : 2020-08-18.109.有序链表转换二叉搜索树
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        list_data = []
        while head:
            list_data.append(head.val)
            head = head.next
        if not list_data:
            return None
        ld = len(list_data)

        def make_tree(data, ld):
            if not data:
                return None
            h = ld//2
            rt = TreeNode(data[h])
            rt.left = make_tree(data[:h], h)
            rt.right = make_tree(data[h+1:], ld-h-1)
            return rt

        root = make_tree(list_data, ld)
        return root


questions = [
    ([-10, -3, 0, 5, 9],),
]

display_list(mk_list(questions[0][0], ListNode))

work(questions, lambda q: Solution().sortedListToBST(mk_list(q[0], ListNode)))
